package com.sheng.leetcode.year2025.month08.day22;

import org.junit.Test;

/**
 * @author by ls
 * @date 2025/8/22
 * <p>
 * 3195. 包含所有 1 的最小矩形面积 I<p>
 * <p>
 * 给你一个二维 二进制 数组 grid。请你找出一个边在水平方向和竖直方向上、面积 最小 的矩形，并且满足 grid 中所有的 1 都在矩形的内部。<p>
 * 返回这个矩形可能的 最小 面积。<p>
 * <p>
 * 示例 1：<p>
 * 输入： grid = [[0,1,0],[1,0,1]]<p>
 * 输出： 6<p>
 * 解释：<p>
 * 这个最小矩形的高度为 2，宽度为 3，因此面积为 2 * 3 = 6。<p>
 * <p>
 * 示例 2：<p>
 * 输入： grid = [[0,0],[1,0]]<p>
 * 输出： 1<p>
 * 解释：<p>
 * 这个最小矩形的高度和宽度都是 1，因此面积为 1 * 1 = 1。<p>
 * <p>
 * 提示：<p>
 * 1 <= grid.length, grid[i].length <= 1000<p>
 * grid[i][j] 是 0 或 1。<p>
 * 输入保证 grid 中至少有一个 1 。<p>
 */
public class LeetCode3195 {

    @Test
    public void test() {
//        int[][] grid = {{0, 1, 0}, {1, 0, 1}};
        int[][] grid = {{0, 0}, {1, 0}};
        System.out.println(new Solution().minimumArea(grid));
    }
}

class Solution {
    public int minimumArea(int[][] grid) {
        // 求出数组中横向和竖向中，第一个 1 和最后一个 1 出现的位置，即可求出长宽
        int x1 = Integer.MAX_VALUE;
        int x2 = 0;
        int y1 = Integer.MAX_VALUE;
        int y2 = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 1) {
                    x1 = Math.min(x1, j);
                    x2 = Math.max(x2, j);
                    y1 = Math.min(y1, i);
                    y2 = i;
                }
            }
        }
        return (x2 - x1 + 1) * (y2 - y1 + 1);
    }
}
